package com.cdream.basic.algorithm.leetcode.tree;

import java.util.LinkedHashMap;
import java.util.Map;

public class Question106 {
    Map<Integer, Integer> inorderMap = new LinkedHashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        for (int i1 = 0; i1 < inorder.length; i1++) {
            inorderMap.put(inorder[i1], i1);
        }
        return buildTree(postorder, inorder, 0, postorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] postorder, int[] inorder, int pLeft, int pRight, int iLeft, int iRight) {
        if (postorder.length == 0) {
            return null;
        }
        if (pLeft > pRight || iLeft > iRight) {
            return null;
        }

        int root = postorder[pRight];
        Integer inorderIdx = inorderMap.get(root);
        // 左子树
        TreeNode lTreeNode = buildTree(postorder, inorder, pLeft, pLeft + (inorderIdx - 1 - iLeft), iLeft, inorderIdx - 1);
        TreeNode rTreeNode = buildTree(postorder, inorder, pLeft + inorderIdx - iLeft, pRight - 1, inorderIdx + 1, iRight);
        return new TreeNode(root,lTreeNode,rTreeNode);

    }
}
